- Title
- Random sampling of trivial words in finitely presented groups
- Creator
- Elder, Murray; Rechnitzer, Andrew; Janse van Rensberg, Esaias J.
- Relation
- Experimental Mathematics Vol. 24, Issue 4, p. 391-409
- Publisher Link
- http://dx.doi.org/10.1080/10586458.2015.1005853
- Publisher
- Taylor & Francis
- Resource Type
- journal article
- Date
- 2015
- Description
- We describe a Metropolis Monte Carlo algorithm for random sampling of freely reduced words equal to the identity in a finitely presented group. The algorithm samples from a stretched Boltzmann distribution [formula could not be replicated] where |w| is the length of a word w, α and β are parameters of the algorithm, and Z is a normalizing constant. It follows that words of the same length are sampled with the same probability. The distribution can be expressed in terms of the cogrowth series of the group, which allows us to relate statistical properties of words sampled by the algorithm to the cogrowth of the group, and hence its amenability. We have implemented the algorithm and applied it to several group presentations including the Baumslag-Solitar groups, some free products studied by Kouksov, a finitely presented amenable group that is not subexponentially amenable (based on the basilica group), the genus 2 surface group, and Richard Thompson's group F.
- Subject
- Metropolis Monte Carlo; algorithm; random sampling; Markov chain
- Identifier
- http://hdl.handle.net/1959.13/1324867
- Identifier
- uon:25144
- Identifier
- ISSN:1058-6458
- Language
- eng
- Reviewed
- Hits: 1267
- Visitors: 1330
- Downloads: 1
| Thumbnail | File | Description | Size | Format |
|---|